package 动态规划.背包And分组And切割问题系列;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/27 9:30
 */
public class leetcode2518好分区的数目 {
    /*
      这个题 主要 是这个 **分组** 的想法。 给一个 nums[] ,一个 k 有点类似于背包了
      因为 就两个组,那样, 我确定 一个 分组 那么另外一个分组 也就确定,
      那么 我求了 一个 分组的 和,那么 另外一个分组的 和, = total - sum(当前的分组和 ) (sum >= k)
     */

    public static final int MOD = (int)1e9 + 7;

    private int k ;
    private int ans;
    public int solution(int nums[],int k){
        this.k = k;
        int sum = 0;
        for(int i : nums){
            sum += i;
        }
        if(sum < 2 * k)
            return 0;
        int len = nums.length;
        return ans;
//        return recursion(0,0,len,sum,nums);
    }
    public int recursion(int index,int curSum ,int len,int sum,int nums[]){
        if(curSum >= k && sum - curSum >= k)
            return 1;
        if(index == len)
            return 0;
        // 涉及到 取 mod 操作 ,直接 把 ans 声明 long 就行,防止出现其他的错误
        long ans = 0;
        ans = recursion(index + 1,curSum + nums[index],len,sum,nums);
        ans += recursion(index + 1,curSum,len,sum,nums);
        return (int) (ans % MOD);
    }

    public void recursionVoid(int index,int curSum ,int len,int sum,int nums[]){
        if(index == len)
            return ;
        // 涉及到 取 mod 操作 ,直接 把 ans 声明 long 就行,防止出现其他的错误
        if(curSum >= k && sum - curSum >= k)
            ans++;
        recursion(index + 1,curSum + nums[index],len,sum,nums);
        recursion(index + 1,curSum,len,sum,nums);
    }

}
